package test3.bit;

/**
 * 268. 丢失的数字
 * <p>
 * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 * <p>
 * 进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
 * <p>
 * 提示：
 * n == nums.length
 * 1 <= n <= 104
 * 0 <= nums[i] <= n
 * nums 中的所有数字都 独一无二
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/missing-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MissingNumber {
    public static void main(String[] args) {
        int[] nums = {2, 0, 1};
        int res = new MissingNumber().missingNumber2(nums);
        System.out.println(res);
    }

    public int missingNumber1(int[] nums) {
        int res1 = 0;
        int res2 = 0;
        for (int i = 0; i < nums.length; i++) {
            res1 += nums[i];
            res2 += i;
        }
        res2 += nums.length;
        return Math.abs(res2 - res1);
    }

    public int missingNumber2(int[] nums) {
        int missNumber = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missNumber ^= nums[i] ^ i;
        }
        return missNumber;
    }

}
